package com.链表2;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 *
 * 说明：不允许修改给定的链表。
 */
public class 环形链表2 {
   static public class Solution {

       public ListNode findCycla(ListNode head){
           ListNode slow = head;
           ListNode fast = head;
           while (fast!=null && fast.next != null){
               slow = slow.next;
               fast = fast.next.next;
               if(slow == fast){
                   return slow;
               }

           }
           return null;
       }
       //找到环，这个很关键
       //找到环后，再找到环的头结点
        public ListNode detectCycle(ListNode head) {
            ListNode  cycle = findCycla(head);
            if(cycle == null){
                return null;
            }
            ListNode slow = head;
            ListNode fast = cycle;
            while (slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;

        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        MyLinkedList link = new MyLinkedList(new int[]{1,2,3});
       // link.addCycle();
        solution.detectCycle(link.head);
    }
}
